1. Field of the Invention
The present invention relates to a scheduler for use in a computer system and also to a scheduling method, and more particularly to a scheduler and a scheduling method in a computer system, in which mutual exclusion of threads or processes is achieved by the use of a shared variable.
2. Description of the Related Art
In a conventional computer system, scheduling is effected such that the CPU time is allocated to processes or users as uniformly as possible. When the conventional scheduling method is applied to parallel programming, a representative example of which is thread programming, the programming cannot be accomplished with high efficiency.
This problem will be described in detail, with reference to FIG. 12 representing the memory space of process which is controlled by a typical conventional operating system (e.g., UNIX operating system). As is shown in FIG. 12, processes 1 and 2 have a text space, a data space, and a stack space each. One of the process cannot refer to any memory space controlled by the other process. Communications between the processes 1 and 2 and the exclusion control thereof are effected by using system calls. The conventional operating system has a large overhead. Hence, it is difficult to prepare such a program as would make a plurality of processors cooperate to perform one processing with high efficiency.
What has been devised to solve this problem is thread programming. FIG. 13 illustrates the memory space for thread programming. A plurality of threads can share a text space, a data space, and a stack space. The threads can, therefore, achieve mutual communications and exclusion control, without using system calls, by the use of variables shared in their memory spaces. In view of this, the thread programming is suitable for a multi-processor system. The threads which shares memory spaces are called a "task" collectively.
A method has been proposed in which a plurality of processes share a memory space as is illustrated in FIG. 14. A shared memory is a special data space which a plurality of processes have in common, and is utilized to accomplish communications between the processes or synchronization of processes.
In thread programming of ordinary type, a variable shared by a plurality of threads is used to achieve exclusion control of threads. Such a shared variable is called a "lock variable." The lock variable is used such that when the lock variable is, for example, "1" one of the threads uses a shared resource exclusively, and any other threads cannot use the shared resource to perform processing.
FIG. 15 schematically shows the thread 3 of task 1 which is exclusively using a shared resource corresponding to a lock variable S (held in lock state). FIG. 15 also shows the other threads 1, 2 and 4 of the task 1 which are waiting for the release of the shared resource (held in lock-wait state).
FIG. 16 is a flow chart explaining how exclusion control (or synchronization control) is carried out, using a lock variable S.
In step S1, a thread reads the lock variable S corresponding to the shared resource in order to perform processing by using a shared resource. In step S2 it is determined whether the value for the lock variable S is "0" or not. If Yes, the flow goes to step S3, in which the lock variable S is rewritten to "1." Then, the thread performs processing via exclusive control of the shared resource. In step S4, upon completion of the processing, the lock variable is rewritten to "0" allowing any other thread to use the shared resource in order to perform processing.
If No in step S2, that is, if the lock variable S is found to have the value of "1" steps S1 and 2 are repeated until the lock variable S acquires the value of "0". The thread remains in so-called "busy-wait state" or "spin-loop state" until the variable S becomes "0".
Steps 1 to 3, i.e., retrieval and up-dating of the lock variable S, need to be executed indivisibly, as test & set instruction should be. Hence, a processor instruction executed to acquire the shared source is basically a single machine instruction.
The use of the lock variable makes it possible to accomplish mutual exclusion of threads, both easily and reliably. In this method, however, the processing efficiency may degrade in some cases where a plurality of threads undergoes frequent mutual exclusion.
In an operating system of ordinary type, for example, a thread is made to stop processing when a predetermined time (i.e., time quantum) elapses or when the processing becomes no longer possible due to I/O waiting or the like, and scheduling is then performed.
Let us assume that the operating system selects the next thread to execute, in the condition illustrated in FIG. 15. Let us also assume that threads 1 to 4 of task 1, thread X of task 2, and threads Y and Z of task 3 have equivalent priority and that they are each executable. In this case, a scheduler can select any one of the threads 1 to 4, but the processing efficiency will greatly differ in accordance with the method of selecting the next thread to execute.
If the system is a single-processor system (having only one CPU), and threads 1, 2 or 4 are selected, the CPU will undergo spin-looping since these threads remain in the lock-wait state, this reducing processing efficiency. If the thread 3 is selected, however, the CPU can perform processing immediately, and the other threads 1, 2 and 4 can start processing the moment the thread 3 finishes processing. In this case, the processing efficiency is high. The CPU is efficiently used when the threads X, Y and Z of the tasks 2 and 3 are executed, as well.
In summary, in the single-processor system, (1) the selecting of a thread in the lock-wait state (i.e., a thread waiting for the release of the shared resource) wastes the CPU time, and (2) the selection of a thread in the lock state (i.e., a thread locking the shared resource) or a thread which need not be set in the lock state can make an effective use of the CPU time. A conventional scheduler cannot determine whether or not a thread is in the lock-wait state. Hence, in some cases, the scheduler may select a thread remaining in the lock-wait state.
FIG. 17 is a diagram representing how the CPU of the single-processor system operates in the case where it takes each thread to complete the execution that must be done exclusively about 1.5 times T, the unit time quantum T. In FIG. 17 the thread 3 locks the shared resource between time t0 and time t1. In this instance, the CPU is sequentially assigned to the threads 1, 2, and 4, each in the lock-wait state during the period between time t1 and t4. Accordingly, it will be used for nothing due to the spin looping. When the thread 3 releases the shared resource at time between t4 and t5, the thread 1 can secure the shared resource for itself during the executing time T elapsing from t5. In the case shown in FIG. 17, the activity ratio of the CPU is 0.5 or less, and the processing efficiency is low.
In a multi-processor system, as well, the same problem will arise. FIG. 18 is diagram explaining the case where threads are sequentially executed with a low efficiency in a multi-processor system which has four CPUs. In this instance, the threads 1, 2, and 4, each remaining in lock-wait state, keeps on spin-looping until the the thread 3 releases the shared resource, and the activity ratio of each CPU is 0.5 or less, too. Obviously, the processing efficiency is low.
The cases explained with reference to FIGS. 17 and 18, respectively, are two of the worst cases. However, phenomena similar to these actually occur in the conventional operating system which employs round robin scheduling.
The scheduling problem explained above arise also when the processes shown in FIG. 14 use the shared variable to achieve mutual exclusion.